package leetcode.editor.vscdev;

import leetcode.editor.utils.*;

//给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
/* 
 * 注意误区:
 *  不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。
 *  比如[5,1,4,null,null,3,6]，虽然3比1小，但是3比5大，所以不是BST。
 *  我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。
 */
class Solution {
    private TreeNode prev = null;
    // DFS递归 按照中序遍历的顺序进行比较 确保节点按升序访问。
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        
        // 遍历左子树
        boolean left = isValidBST(root.left);
        if (!left) return false;

        // 中 访问当前节点：如果当前节点的值不大于前一个节点的值，则不是BST
        if (prev != null && prev.val >= root.val) return false;
        prev = root;

        // 遍历右子树
        boolean right = isValidBST(root.right);
        return right;
    }
}